package sword.T59;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 18362
 * @Create: 2022-04-10 14:50:22 星期日
 */
public class MaxQueue {

    class Node {
        int seq;
        int value;

        public Node(int seq, int value) {
            this.seq = seq;
            this.value = value;
        }
    }

    private Deque<Node> dq = new LinkedList<>();
    Queue<Node> queue = new LinkedList<>();
    private int seq = 0;

    public MaxQueue() {
    }

    public int max_value() {
        if (queue.isEmpty())
            return -1;
        return dq.getFirst().value;
    }

    public void push_back(int value) {
        while (!dq.isEmpty() && dq.getLast().value <= value)
            dq.removeLast();
        dq.addLast(new Node(seq, value));
        queue.offer(new Node(seq, value));
        seq++;
    }

    public int pop_front() {
        if (queue.isEmpty())
            return -1;
        Node node = queue.poll();
        if (node.seq == dq.getFirst().seq)
            dq.removeFirst();
        return node.value;
    }
}
